package leetcode.Hot100;

import leetcode.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Cheng Jun
 * Description: 给定一个二叉树，检查它是否是镜像对称的。
 * https://leetcode-cn.com/problems/symmetric-tree/
 * 你可以运用递归和迭代两种方法解决这个问题吗？
 * @version 1.0
 * @date 2021/12/3 21:27
 * 二刷
 */
public class isSymmetric {

    // 广度优先搜索，逐层校验
    static boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 存放该层所有 Node 的容器（容器大小 2^(n-1)） ArrayList
        // 容器确认是否镜像对称
        // 对称找下一层
        boolean flag = true;
        int n = 0;
        ArrayList<TreeNode> nodeList = new ArrayList<>((int) Math.pow(2, n));
        nodeList.add(root);
        while (nodeList.size() > 0) {
            for (int i = 0; i < nodeList.size() / 2; i++) {
                if (nodeList.get(i) == null && nodeList.get(nodeList.size() - i - 1) == null) {
                    continue;
                }
                if (nodeList.get(i) != null && nodeList.get(nodeList.size() - i - 1) == null) {
                    flag = false;
                    break;
                }
                if (nodeList.get(i) == null && nodeList.get(nodeList.size() - i - 1) != null) {
                    flag = false;
                    break;
                }
                if (nodeList.get(i).val != nodeList.get(nodeList.size() - i - 1).val) {
                    flag = false;
                    break;
                }
            }
            if (!flag) {
                break;
            }
            ArrayList<TreeNode> nextNodeList = new ArrayList<>((int) Math.pow(2, ++n));
            for (TreeNode treeNode : nodeList) {
                if (treeNode != null) {
                    nextNodeList.add(treeNode.left);
                    nextNodeList.add(treeNode.right);
                }
            }
            nodeList = nextNodeList;
        }
        return flag;
    }

    // 深度优先搜索（借助 LinkedList 实现，优化上面的空间复杂度）
    static boolean isSymmetric1(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean flag = true;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root.left);
        deque.add(root.right);
        while (!deque.isEmpty()) {
            TreeNode t1 = deque.poll();
            TreeNode t2 = deque.poll();
            if (t1 == null && t2 == null) {
                continue;
            }
            if (t1 == null || t2 == null) {
                flag = false;
                break;
            }
            if (t1.val != t2.val) {
                flag = false;
                break;
            }
            deque.add(t1.left);
            deque.add(t2.right);
            deque.add(t1.right);
            deque.add(t2.left);
        }
        return flag;
    }

    // 递归算法：这个题的递归有点技巧
    // 分析：把 root 的两个子树 看做 两棵 独立的树 A1 A2， A1 == A2，再比较 A1.left 与 A2.right， A1.right 与 A2.left
    // 提交LeetCode 时间复杂度最优。
    static boolean isSymmetric2(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return compare(root.left, root.right);
        }
    }

    static boolean compare(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return true;
        }
        if (t1 == null || t2 == null) {
            return false;
        }
        return t1.val == t2.val && compare(t1.left, t2.right) && compare(t1.right, t2.left);
    }
}
